# -*- coding: utf-8 -*-
'''
@author: Luís Shou nº 5601
@date: Maio de 2013
'''

class HeapSort:
  '''
  Classe do algoritmo bubbleSort
  '''
  def __init__(self, A):
    '''
    Construtor da classe.
    Parametros de entrada: 
      'A'- Lista com elementos a ordenar
    '''
    self.A = A
    self.heapsize = len(self.A)
    self.heapsort()
    pass

  def left(self, i):
    '''
    Retorna o nó esquerdo
    Parametros de entrada:
      'i' - indice da tabela
    '''
    return ((2 * i) + 1)
    pass

  def right(self, i):
    '''
    Retorna o nó direito
    Parametros de entrada:
      'i' - indice da tabela
    '''
    return ((2 * i) + 2)
    pass


  def max_heapify(self, i):
    '''
    Método que mantem a propriedade de max-heap
    ou seja, o valor mais elevado está guardado no nó raiz

    Parametros: 
      'i' - indice da tabela
    '''
    l = self.left(i)
    r = self.right(i)
    largest = 0
    if l < self.heapsize and self.A[l] > self.A[i]:
      largest = l
    else:
      largest = i

    if r < self.heapsize and self.A[r] > self.A[largest]:
      largest = r

    if largest != i:
      self.A[i], self.A[largest] = self.A[largest], self.A[i]
      self.max_heapify(largest)

    pass

  def build_max_heap(self):
    '''
    Este metedo constrói uma 'heap' através do tamanho da lista recebida
    '''
    for k in range(len(self.A) / 2, -1, -1):
      self.max_heapify(k)
      pass
    pass

  def heapsort(self):
    '''
    Metodo que 'pede' para contruir a heap e ordena os nós
    '''
    self.build_max_heap()
    for k in range(len(self.A) - 1, 0, -1):
      temp = self.A[k]
      self.A[k] = self.A[0]
      self.A[0] = temp
      self.heapsize = self.heapsize - 1
      self.max_heapify(0)
      pass
    pass
  pass
